BOJ28246 돌 가져가기 게임

풀이

수열a와 시작위치(i와 i+1사이)가 주어지면 A,B중에 누가 이기는지를 먼저 생각해봅시다.

일단 n이 홀수인 경우 선공은 아무방향으로나 모든 돌을 제거하면, 게임판은 길이가 짝수인 string형태가 됩니다. 이때 후공이 모든돌을 먹지 않고 움직인다면, 선공이 왔던방향으로 모든 돌을 먹어서 되돌려 보내면 후공은 고립되서 지게 됩니다. 따라서 후공은 무조건 모든 돌을 먹어야 하고, 선공도 모든 돌을 먹는거로 대응하면 홀짝성에 의해 항상 후공이 집니다.

n이 짝수인 경우, 선공이 모든 돌을 먹어서 움직이면 길이가 홀수인 string이 되고, N이 홀수인 경우에서 논의한 홀짝성에 의해 이번엔 후공이 승리하게 됩니다. 따라서 선공은 항상 모든 돌을 가져가면 안됩니다. 그럼 선공이 한개만 남기고 모든 돌을 가져간다면 어떨까요? 후공도 돌을 한개만 남기고 모든 돌을 가져가는것으로 맞대응하면 N이 짝수이므로 모든 돌이 1이 된 이후에 선공이 먼저 움직여야하고, 1개(이상)의 돌을 가져가야만 하므로 선공이 패배합니다. 단, 이는 모든 돌이 1초과일때만 가능한데 그 이유는 돌이 1개뿐인곳에서는 반드시 모든 돌을 가져가야 하기 때문입니다. 같은 논리로 2개남기고 움직이는 전략은 모든 돌이 2초과일때 선공이 패배하고, 이를 계속진행하면 최소값 미만의 돌을 남기는 전략은 항상 패배함을 알 수 있습니다. (최소값 자신은 최소값 초과는 아니기 때문에 위의 논의는 최소값 미만에서 끝남) 따라서 돌을 최소값 이상 남기고 전부 가져가는게 선공의 전략 후보입니다. 그런데 최소값초과를 가져가면 후공이 최소값을 남기며 이전위치로 되돌려보낼 수 있고, 선공은 다시는 그 방향으로 갈 수 없습니다. 왜냐하면 그 방향으로 가려면 최솟값 미만을 만들게되서 패배하기 때문입니다. 따라서 선공은 항상 최솟값만큼만 남기며 움직이는게 최적입니다. 후공도 비슷한 논리로 최솟값만 남기며 이동하는게 최적입니다.

위에서 구한 최적전략에서 (선공의) 승리지점은 다음과 같은걸 쉽게 알 수 있습니다. 최소값을 제거하여 만들어지는 string들에 대해 string의 길이를 연속한 (최소값 초과인)숫자들 개수라고 정의할때 홀수길이 string은 모든지점에서, 짝수길이 string에선 len/2개의 승리지점이 있습니다.

이제 후공이 k개의 돌을 사용해서 string을 연결할 때 선공의 승리지점을 최소화 하는 문제를 풀 수 있다면, 문제를 해결할 수 있습니다. 이를 위해 다음과 같은 관찰이 필요합니다. 일단, 짝수string이 하나라도 존재한다면, 그와 인접한 홀수string은 돌 하나를 사용해서 짝수string으로 만들어 줄 수 있어서 선공의 승리지점개수가 감소합니다. 이제 string들의 배열에서 k개의 돌을 사용해서 짝수string에 (인접한)홀수string들을 붙여줄때 선공 승리지점을 최소화 하는 문제가 되고, 이는 Knapsack으로 O(N^2)정도에 해결할 수 있습니다.

A[i]보다 작은 값은 미리 돌을 채워서 A[i]가 최솟값일때를 가정하고 위의 로직을 진행하는걸 N가지 경우에 대해 모두 처리해주면 총 O(N^3)정도에 문제를 풀 수 있습니다.

여담

원래 검수자가 아니었는데, BOJ공개되기전에 솗닥 디코에 KOISTUDY링크 올라온거 풀면서 셀프저격용 데이터 추가했더니 검수자로 넣어버리셨다 ㄷㄷ..